/*
 * @lc app=leetcode.cn id=15 lang=cpp
 *
 * [15] 三数之和
 */

// @lc code=start
class Solution
{
public:
    vector<vector<int>> threeSum(vector<int> &nums)
    {
        //三数之和
        //具体思路是固定第一个数 然后用双指针查找后两个数之和
        //因为需要去重 所以移动数字的时候如果数字相同就跳过
        vector<vector<int>> res; //存储结果
        if (nums.size() < 3)
        {
            return res; //先剪枝
        }
        sort(nums.begin(), nums.end()); //排序
        int first = 0;                  //固定指针
        for (first = 0; first < nums.size(); first++)
        {
            class Solution
            {
            public:
                vector<vector<int>> threeSum(vector<int> &nums)
                {
                    //三数之和
                    //具体思路是固定第一个数 然后用双指针查找后两个数之和
                    //因为需要去重 所以移动数字的时候如果数字相同就跳过
                    vector<vector<int>> res; //存储结果
                    if (nums.size() < 3)
                    {
                        return res; //先剪枝
                    }
                    sort(nums.begin(), nums.end()); //排序
                    int first = 0;                  //固定指针
                    for (first = 0; first < nums.size(); first++)
                    {
                        //如果第一个已经大于0了 直接跳过
                        if (nums[first] > 0)
                        {
                            return res;
                        }
                        //如果first与上一个相同跳过当前循环
                        if (first != 0 && nums[first - 1] == nums[first])
                        {
                            continue;
                        }

                        //固定指针 后面两个指针移动
                        int second = first + 1;
                        int third = nums.size() - 1;
                        //同样的 为了避免重复 如果与下一个元素相同 直接跳过
                        while (second < third && nums[second] == nums[second + 1])
                        {
                            second++;
                        }
                        while (second < third && nums[third] == nums[third - 1])
                        {
                            third--;
                        }
                        //开始寻找三元组
                        while (second < third)
                        {
                            //如果写成三数之和可能导致溢出
                            if (nums[second] + nums[third] > -nums[first])
                            {
                                //过大 移动右指针
                                third--;
                            }
                            else if (nums[second] + nums[third] < -nums[first])
                            {
                                //过小 移动左指针
                                second++;
                            }
                            else
                            {
                                //找到了三元组 按照顺序存入res
                                res.push_back({nums[first], nums[second], nums[third]});
                            }
                        }
                    }
                    return res;
                }
            };
            //如果first与上一个相同跳过当前循环
            if (first != 0 && nums[first - 1] == nums[first])
            {
                continue;
            }
            //如果第一个已经大于0了 直接跳过
            if (nums[first] > 0)
            {
                continue;
            }
            //固定指针 后面两个指针移动
            int second = first + 1;
            int third = nums.size() - 1;
            //同样的 为了避免重复 如果与下一个元素相同 直接跳过
            while (second < third && nums[second] == nums[second + 1])
            {
                second++;
            }
            while (second < third && nums[third] == nums[third - 1])
            {
                third--;
            }
            //开始寻找三元组
            while (second < third)
            {
                //如果写成三数之和可能导致溢出
                if (nums[second] + nums[third] > -nums[first])
                {
                    //过大 移动右指针
                    third--;
                }
                else if (nums[second] + nums[third] < -nums[first])
                {
                    //过小 移动左指针
                    second++;
                }
                else
                {
                    //找到了三元组 按照顺序存入res
                    res.push_back({nums[first], nums[second], nums[third]});
                }
            }
        }
        return res;
    }
};
// @lc code=end
